// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "leveldb/filter_policy.h"

#include "leveldb/slice.h"
#include "util/hash.h"

namespace leveldb {

namespace {
static uint32_t BloomHash(const Slice& key) {
  return Hash(key.data(), key.size(), 0xbc9f1d34);
}

/*
 * 布隆过滤器的存储空间大小m，哈希函数个数k和元素总的个数n之间存在一个计算公式: k = (m/n) * In2
 * 假设空间大小m确定，并且元素总个数n也能够得出，那么应用该公式可以得出一个误报率最低的k值。
 */
class BloomFilterPolicy : public FilterPolicy {
 public:
  explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    // 通过公式(k = (m/n) * In2)计算每个键需要进行哈希的次数，并将该次数保存到变量k_中。
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;
  }

  const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }

  // 创建一个布隆过滤器，keys代表布隆过滤器中要插入的元素数组，n代表参数keys中共有多少元素，dst放置最后生成的布隆过滤器内容。
  void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
    // Compute bloom filter size (in both bits and bytes)
    size_t bits = n * bits_per_key_;  // n * m/n = m

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;

    size_t bytes = (bits + 7) / 8;
    bits = bytes * 8;

    // 生成过滤器内容并保存到dst参数中，将k_值压入dst中
    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, 0);
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
    char* array = &(*dst)[init_size];
    //依次处理每一个键。
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {  //理论上需要对每一个键计算k_次哈希值，此处通过将对键计算得到的哈希值加delta值来模拟哈希运算。
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }
  
  // 通过过滤器判断一个键是否存在，key为需要判断是否存在的键，bloom_filter为过滤器的内容。
  bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
    const size_t len = bloom_filter.size();
    if (len < 2) return false;  //布隆过滤器尾部是k_的值，因此需要大于1字节。

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len - 1];
    if (k > 30) {
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }

    uint32_t h = BloomHash(key);  // 计算键的哈希值。
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    //原理同创建布隆过滤器，判断布隆过滤器中的相应位置是否置为1，有任意一位为0则返回false。否则返回true。
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;
      if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
      h += delta;
    }
    return true;
  }

 private:
  size_t bits_per_key_;  // 代表每个元素需要使用的位个数，即m/n。
  size_t k_;  // 每个键需要进行哈希的次数。
};
}  // namespace

const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
  return new BloomFilterPolicy(bits_per_key);
}

}  // namespace leveldb
